package leetcode_700;

/**
 *@author 周杨
 *ImplementMagicDictionary_676 给定一个字典 查询的时候可以改变字典里的某一个字母 实现这样的数据结构
 *describe:用前缀树 AC 5%
 *2018年10月6日 下午3:49:43
 */
public class ImplementMagicDictionary_676 {
	 class TrieNode {
	        TrieNode[] children = new TrieNode[26];
	        boolean isWord;
	        public TrieNode() {}
	    }
	    TrieNode root;
	    /** Initialize your data structure here. */
	    public ImplementMagicDictionary_676() {
	        root = new TrieNode();
	    }
	    
	    /** Build a dictionary through a list of words */
	    public void buildDict(String[] dict) {
	        for (String s : dict) {
	            TrieNode node = root;
	            for (char c : s.toCharArray()) {
	                if (node.children[c - 'a'] == null) {
	                    node.children[c - 'a'] = new TrieNode();
	                }
	                node = node.children[c - 'a'];
	            }
	            node.isWord = true;
	        }
	    }
	    
	    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
	    public boolean search(String word) {
	        char[] arr = word.toCharArray();
	        for (int i = 0; i < word.length(); i++) {
	            for (char c = 'a'; c <= 'z'; c++) {
	                if (arr[i] == c) {
	                    continue;
	                }
	                char org = arr[i];
	                arr[i] = c;
	                if (helper(new String(arr), root)) {
	                    return true;
	                }
	                arr[i] = org;
	            }
	        }
	        return false;
	    }
	    public boolean helper(String s, TrieNode root) {
	        TrieNode node = root;
	        for (char c : s.toCharArray()) {
	            if (node.children[c - 'a'] == null) {
	                return false;
	            }
	            node = node.children[c - 'a'];
	        }
	        return node.isWord;
	    }
}
